package demo6;

//牛客网:腐烂的苹果
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param grid int整型ArrayList<ArrayList<>> 
     * @return int整型
     */
    public int rotApple (ArrayList<ArrayList<Integer>> grid) {
        Queue<int[]> queue = new LinkedList<>();
        int n = grid.size();
        int m = grid.get(0).size();
        boolean[][] st = new boolean[n][m];
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid.get(i).get(j) == 2) {
                    st[i][j] = true;
                    queue.add(new int[]{i,j});
                }
            }
        }
        int[] xx = {1,-1,0,0};
        int[] yy = {0,0,1,-1};
        int ret = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i<size; i++) {
                int[] peek = queue.poll();
                int x = peek[0], y = peek[1];
                for(int j = 0; j<4; j++) {
                    int dx = x + xx[j];
                    int dy = y + yy[j];
                    if(dx >=0 && dx < n && dy >= 0 && dy < m && grid.get(dx).get(dy) == 1 && !st[dx][dy]) {
                        queue.add(new int[]{dx,dy});
                        st[dx][dy] = true;
                    }
                }
            }
            ret++;
        }

        for(int i = 0; i<n; i++) {
            for(int j = 0; j<m; j++) {
                if(grid.get(i).get(j) == 1 && !st[i][j]) {
                    System.out.println(i+" "+j);
                    return -1;
                }
            }
        }

        return ret-1;
    }
}